#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <alloc.h>

#include "graph.h"

/* Duyet cau truc danh sach ke voi nhung dinh u ma(u,v) la canh */
typedef struct successors {
       int d;          /* so cac dinh trong danh sach ke (degree) */
       int len;        /* so cac slot trong mang danh sach */
       char is_sorted; /* true = 1, neu danh sach da duoc sap xep */
       int list[1];    /* danh sach cac dinh ke hien tai */
} Adjacent_list;

/* Xet tren lop Do thi vo huong */
struct graph {
       int nVertex;           /* so cac dinh */
       int nEdge;             /* so cac canh */
       Adjacent_list *alist[1]; /* Tap cac danh sach ke */
};

/* Dinh nghia dinh 
typedef struct {
    int * label;
    int adjlist[1];    // danh sach cac dinh ke hien tai 

} Vertex;

// Dinh nghia canh 
typedef struct {
    Vertex *source;
    Vertex *target;
    float weight; // Khong su dung
} Edge;

*/

/* Tao Do thi n dinh voi cac nhan tu 0...n-1, tap canh la rong */
Graph graph_create(int n)
{
      Graph g;
      int i;
      g = malloc(sizeof(struct graph) + (n-1) * sizeof(Adjacent_list));
      assert(g);
      
      g->nVertex = n;
      g->nEdge = 0;
      
      for(i=0;i<n;i++)
      {
           g->alist[i] = malloc(sizeof(Adjacent_list));
           assert(g->alist);
           
           g->alist[i]->d = 0;
           g->alist[i]->len = 1;
           g->alist[i]->is_sorted= 1;
      }
      
      return g;
} // end graph_create()

/* Huy Do thi */
void graph_destroy(Graph g)
{
     int i;
     
     for(int i = 0; i < g->nVertex ;i++) free(g->alist[i]);
     free(g);
} // end graph_destroy()

/* Them canh vao Do thi */
void graph_add_edge(Graph g, int s, int t)
{
     assert(s>=0);
     assert(s<g->nVertex);
     assert(t>=0);
     assert(t<g->nVertex);
     
     while(g->alist[s]->d > g->alist[s]->len)
     {
           g->alist[s]->len *=2;
           g->alist[s]=realloc(g->alist[s],sizeof(Adjacent_list)+
                               sizeof(int) * (g->alist[s]->len - 1));
     }
     
     g->alist[s]->list[g->alist[s]->d++] = t;
     g->alist[s]->is_sorted = 0;
     
     /* Dem lai canh */
     g->nEdge++;
} // end graph_add_edge()

/* Tra ve so dinh cua do thi */
int graph_vertex_count(Graph g)
{
    return g->nVertex;
}

/* Tra ve bac cua mot dinh */
int graph_out_degree(Graph g, int source)
{
    assert(source >= 0);
    assert(source <g->nVertex);
    
    return g->alist[source]->d;
}

/* Su dung ham bsearch() cho nhung truong hop so lon */
#define BSEARCH_THRESHOLD (10)

static int intcmp(const void *a, const void *b)
{
       return *((const int *) a) - *((const int *) b); 
}

/* Tra ve 1, neu ton tai canh (source, sink), nguoc lai tra ve 0 */
int graph_has_edge(Graph g, int source, int sink)
{
    int i;
    
    assert(source >= 0);
    assert(source < g->nVertex);
    assert(sink >= 0);
    assert(sink < g->nVertex);
    
    if(graph_out_degree(g,source) >= BSEARCH_THRESHOLD){
          /* Sap xep lai danh sach */
          if(! g->alist[source]->is_sorted){
               qsort(g->alist[source]->list, g->alist[source]->d, 
                                sizeof(int), intcmp);
          }
          
          return bsearch(&sink, g->alist[source]-> list,
                                g->alist[source]->d, 
                                sizeof(int), intcmp)
                  != 0;
    } else {
           for(i = 0; i < g->alist[source]->d;i++){
                 if(g->alist[source]->list[i] == sink) return 1;
           }
           /* khong tim thay */
           return 0;
    }
} // end graph_has_edge()
